package com.jc.projecteuler.january;


/**
 * A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
 * <p>
 * Find the largest palindrome made from the product of two 3-digit numbers.
 *
 * 方法1. 是使用字符串的形式去判断，性能较差
 * 方法2. 转换为数字判断，性能已经不错了
 * 方法3. 过滤掉一些没必要的数字
 *
 * 总结: 把问题转为数学问题, 性能会突增
 */
public class Problem4 {

    public static void main(String[] args) {

        int max = 0;
        long begin = System.currentTimeMillis();
        for (int i = 100; i < 1000; i++) {
            for (int j = 100; j < 1000; j++) {
                int product = i * j;

                if (isPalindrome(product)) {
                    if (product > max)
                        max = product;
                }

            }
        }
        //the largest palindrome is 906609 cost 217ms
        System.out.println("Method1. the largest palindrome is " + max + " cost " + (System.currentTimeMillis() - begin) + "ms");

        max = 0;
        long begin2 = System.currentTimeMillis();
        for (int i = 100; i < 1000; i++) {
            for (int j = 100; j < 1000; j++) {
                int product = i * j;

                if (isPalindrome2(product)) {
                    if (product > max)
                        max = product;
                }

            }
        }
        System.out.println("Method2. the largest palindrome is " + max + " cost " + (System.currentTimeMillis() - begin2) + "ms");


        max = 0;
        long begin3 = System.currentTimeMillis();
        for (int i = 100; i < 1000; i++) {
            for (int j = i; j < 1000; j++) {
                int product = i * j;

                if (product > max && isPalindrome2(product)) {
                    max = product;
                }

            }
        }
        System.out.println("Method3. the largest palindrome is " + max + " cost " + (System.currentTimeMillis() - begin3) + "ms");
    }

    /**
     * output:
     * Method1. the largest palindrome is 906609 cost 219ms
     * Method2. the largest palindrome is 906609 cost 24ms
     * Method3. the largest palindrome is 906609 cost 8ms
     */

    private static boolean isPalindrome(Integer product) {
        String pStr = product.toString();
        StringBuilder sb = new StringBuilder(pStr);
        String pStrReverse = sb.reverse().toString();//将str倒置的方法

        if (pStr.equals(pStrReverse)) {
            return true;
        } else {
            return false;
        }
    }

    private static boolean isPalindrome2(int product) {
        return product == reverse(product);
    }

    private static int reverse(int product) {
        int reversed = 0;
        while (product > 0) {
            reversed = 10 * reversed + product % 10;
            product = product / 10;
        }
        return reversed;
    }


}
